﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你⼀个按照⾮递减顺序排列的整数数组nums，和⼀个⽬标值target。请你找出给定⽬标值在数组中的开始位置和结束位置。
//如果数组中不存在⽬标值target，返回[-1,  - 1]。
//你必须设计并实现时间复杂度为O(logn)的算法解决此问题。
//eg:输⼊：nums = [5, 7, 7, 8, 8, 10], target = 8  输出：[3, 4]
#include <iostream>
using namespace std;

//两次二分，时间复杂度为logN
void SearchRange(int* a,int n,int t)
{
	int left = 0, right = n-1;
	//找左端点
	while (left<right)//取等，会出现死循环
	{
		int mid=left+(right-left)/2;//注意中点的选取，和右端点的情况不一样，避免出现死循环
		if (a[mid] < t)
		{
			left = mid + 1;
		}
		else if(a[mid]>=t)
		{
			right = mid;
		}
	}
	if (a[left] != t)//判断最终找到的那个符合条件的数是否就是那个数
	{
		cout << "-1 -1" << ' ';
	}
	else
		cout << left << ' ';


	//找右端点
	left = 0, right = n - 1;
	while (left < right)
	{
		int mid= left + (right - left+1) / 2;//注意中点的选取
		if (a[mid] <= t)
		{
			left = mid;
		}
		else if (a[mid] > t)
		{
			right = mid-1;
		}
	}
	if (a[right] == t)//这里其实可以不用判断，因为已经找到左端点了，无论如何右端点都存在
		cout << right << ' ';
}

int main()
{
	int nums[] = { 5, 7, 8,8,8,8,8, 8, 8, 10 }, target = 8;
	int n = sizeof(nums) / sizeof(nums[0]);
	for (int i = 0; i < n; i++)
	{
		cout << nums[i] << ' ';
	}
	cout << endl;

	SearchRange(nums, n, target);

	return 0;
}